package com.hr.leetcode.树和二叉树和二叉搜索树;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 周恒哲
 * @date 2020/05/16
 **/
public class _98_验证二叉搜索树 {
    //1、中序遍历一
    List<Integer> res=new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        inOrder(root);
        for (int i = 1; i < res.size(); i++) {
            if (res.get(i)<=res.get(i-1)){
                return false;
            }
        }
        return true;
    }
    private void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        isValidBST(root.left);
        res.add(root.val);
        isValidBST(root.right);
    }
    //2、中序遍历二
    public boolean isValidBST2(TreeNode root) {
        long pre = Long.MIN_VALUE;//最小值
        if (root == null) {
            return true;
        }//若树为空，是二叉搜索树（BST）
        // 访问左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if (root.val <= pre) {
            return false;
        }
        //每一个节点
        pre = root.val;
        // 访问右子树
        return isValidBST(root.right);
    }
    //3、利用二叉排序树性质，左边的最大值小于根，右边的最小值大于根
    public boolean isValidBST3(TreeNode root) {
        return validate(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    private boolean validate(TreeNode root,long min,long max){
        if (root==null){
            return true;
        }
        if (root.val<=min || root.val>=max){
            return false;
        }
        return validate(root.left, min, root.val)&&validate(root.right, root.val, max);
    }
}